1. Field of the Invention
The present invention relates to a method for automatically optimizing element placement by using a computer in the layout design of a semiconductor device.
2. Description of the Prior Art
The problem of optimization of element placement in a semiconductor results in a problem of searching for a placement to minimize a given cost function. The cost function herein denotes a function in which a value is uniquely determined with respect to one placement and also is referred to as an optimization object function. The cost function is defined appropriately in accordance with individual specific problems. The cost function differs depending on problems, for example, a problem of a placement of standard cells in a block, a problem of a placement of a transistor in the standard cell, or the like.
As a means for heuristically solving the optimization problem of element placement in a semiconductor with a defined cost function to be minimized using a computer, a method of assuming a combinatorial problem to be a physical system and of performing the generation of a thermal equilibrium condition by Monte-Carlo simulation under the control with a virtual temperature parameter is well known (S. Kirkpatrick et al. xe2x80x9cOptimization by Simulated Annealingxe2x80x9d, SCIENCE, Vol. 220, No. 4598, pp. 671-680, 1983). That is, under a constant virtual temperature, by performing the Monte-Carlo simulation in which a random placement change and a judgement whether the placement change is accepted under a rule set by analogy to statistical physics are repeated, a thermal equilibrium condition corresponding to the virtual temperature is generated and the thermal equilibrium condition is generated at each virtual temperature while slowly cooling from a high temperature to a cryogenic temperature (absolute temperature of about 0xc2x0 C.), and finally an approximate minimum solution to the cost function is obtained. Such a method generally is referred to as a simulated annealing method (hereinafter, referred to as SA method), and broadly used for practically treating actual optimization problems of element placement.
The performance of the SA method is evaluated by a total repetition number of searches, which is a total sum of the repetition number of searches required at the time of Monte-Carlo simulation at all virtual temperatures, and an error between the cost function value of the final solution and the real minimum value of the cost function value. The speed of the optimization processing becomes high as the total repetition number becomes small, and the quality of solution becomes high as the error between the cost function value of the final solution and the real minimum value of the cost function value becomes small.
The technique for generating thermal equilibrium condition by the Monte-Carlo simulation under a constant virtual temperature is one of the important elementary techniques of the SA method. The precision of the thermal equilibrium achieved by the generation of the thermal equilibrium condition largely affects the quality of the final solution of the SA method. Furthermore, if the number of temperature points for observing the thermal equilibrium during the slow cooling process in the SA method is decreased, the effect of the precision of the thermal equilibrium at one temperature on the quality of the final solution is increased. Therefore, whether it is possible to achieve the precise thermal equilibrium by the generation of the thermal equilibrium condition involves not only the quality of the final solution but also the improvement of total processing efficiency in SA method, and is very important in performing the SA method. Therefore, in generating the thermal equilibrium condition, it is desired to generate a precise thermal equilibrium condition with a small repetition number of searches.
The conventional method for optimizing element placement in order to generate the thermal equilibrium conditions includes, for example, a method called a Metropolis method among the Monte-Carlo simulation methods. In generating the thermal equilibrium condition by the Metropolis method, the following Monte-Carlo simulation is carried out. When the cost function value is defined as Ej for a placement Sj that is jth generated at one virtual temperature T, and the cost function value is defined as Ej+xcex94E for a placement Sjxe2x80x2 that is locally changed from the placement Sj, the placement Sjxe2x80x2 is accepted as the (j+1)th placement at a probability of 1 if xcex94Exe2x89xa60, while if xcex94E greater than 0, at a probability expressed by exp (xe2x88x92xcex2xc3x97xcex94E), wherein k denotes a virtual temperature normalization constant, and xcex2 denotes an amount that is in proportion to the reciprocal of the virtual temperature and is defined as xcex2=1/(kxc3x97T).
Furthermore, another conventional method for optimizing element placement includes a method in which, in order to generate a thermal equilibrium condition, for example, by converging the average value of the cost function value for a placement generated at one virtual temperature T, the achievement of equilibrium is judged (Kurokawa et al. xe2x80x9cMethod for optimizing a placement by simulated phase transition method,xe2x80x9d the 12th workshop (Karuizawa) xe2x80x9cCircuit and Systemxe2x80x9d pp. 451-456, 1999). In this method, in judging the convergence of the average value as the statistic, repetition placement search operations in order to generate placements sequentially are composed of repetition operations in a two-level hierarchy consisting of higher and lower levels; and each time a series of repetition searches in each of the lower levels are finished, the convergence of the average value in the lower level is judged.
In a case of the SA method using Monte-Carlo simulation by the Metropolis method for generating a thermal equilibrium condition as in the above-mentioned conventional method for optimizing element placement, since the Metropolis method is one of the approximate techniques for achieving the thermal equilibrium and gives precedence to the relief of a burden on the computer, it has a problem in sacrificing the precision of the thermal equilibrium.
Furthermore, as in the above-mentioned another modification method for element placement, the SA method in which the judgement of the thermal equilibrium is carried out by the convergence of the average value of the cost function values does not conform to the essential meaning of the physical thermal equilibrium. Also this method gives precedence to the relief of the burden on a computer, and thus sacrifices the precision of the thermal equilibrium. Furthermore, the judgement of the thermal equilibrium is carried out in which the convergence of the average value in the lower level while using the repetition operations of the two-level hierarchy is judged, so that it is necessary to increase the number of repetition in the lower level for actually observing the convergence of the average values, thus lowering the efficiency in generating the thermal equilibrium condition.
With the foregoing in mind, it is an object of the present invention to provide a method for optimizing element placement, which improves a method for judging whether a placement change is accepted at the time of generating thermal equilibrium and a method for achieving thermal equilibrium and generates the thermal equilibrium condition with high efficiency and high precision, thereby shortening the processing time by the SA method and improving the optimality of solution.
In order to achieve the above-mentioned object, a method for optimizing element placement according to the present invention is a method for optimizing element placement in layout design of a semiconductor device, and includes: generating a thermal equilibrium condition by performing a Monte-Carlo simulation at each virtual temperature while varying the virtual temperature that is a parameter for controlling a range in which a solution of element placement on a placement expression space is searched, thereby uniquely calculating a cost function value for evaluating the element placement with respect to an individual placement of elements; and searching an optimal placement solution to minimize the cost function value, wherein: the thermal equilibrium condition is generated by performing the Monte-Carlo simulation in which a placement Sjxe2x80x2 is accepted as the (j+1)th placement at a probability of w expressed by the following relationship:
w=1/(exp(xcex94E/(kxc3x97T))+1)
wherein a cost function value for the jth placement Sj generated at one virtual temperature T is calculated as Ej, and a cost function value calculated for a placement Sjxe2x80x2 obtained by locally changing the placement Sj is varied by only xcex94E into Ej+xcex94E, and k denotes a normalization constant at a virtual temperature T.
With this method, by judging whether the change is accepted faithfully to the physical understanding of nature, it is possible to generate the thermal equilibrium condition in a middle temperature region in which the reduction amount of the cost function value with respect to the decrease in the virtual temperature is maximum with high precision and to achieve a final solution with higher quality.
In the above-mentioned method for optimizing element placement, it is preferable that in generating the thermal equilibrium condition, judgement of convergence is carried out by a distributed value of the cost function value for the placement generated at one virtual temperature T, and judgement whether the thermal equilibrium is achieved is carried out based on the results of the convergence judgment.
With such a method, for the cost function value, by calculating the distribution that is a macro amount in proportion to a measurable specific heat of the physical system instead of the average of energy of the physical system, which is a non-measurable macro amount, and judging its convergence, the judgement of thermal equilibrium can be carried out faithfully to the physical understanding of nature.
In this case, it is preferable that the generation of the thermal equilibrium condition comprises repetition searches for placements consisting of a two-level hierarchy of higher and lower levels for generating element placements sequentially; judges the convergence of one statistic of the cost function value in the higher level each time a series of repetition placement searches in the lower level is finished; and judges the achievement of the thermal equilibrium based on the result of the convergence judgement.
With this method, even the statistic that is distribution of the cost function value, which conventionally has been difficult to be converged, can be converged by accumulating a set of the cost function values, when accumulation frequency of the cost function values becomes large, even if the fluctuation of the distribution is large around the phase transition temperature in which the optimization advances rapidly. Therefore, it is possible to improve the efficiency in generating the thermal equilibrium condition.